Search for: All records

The epsilon-approximate degree, deg_epsilon(f), of a Boolean function f is the least degree of a real-valued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly k-wise indistinguishable, but are distinguishable by f with advantage 1 - epsilon. Our contributions are: - We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilon-approximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3-approximate degree of any (possibly unbalanced) read-once DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anti-concentration of the Binomial distribution. - We show that any pair of symmetric distributions on n-bit strings that are perfectly k-wise indistinguishable are also statistically K-wise indistinguishable with at most K^{3/2} * exp (-Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size-K coalitions with statistical error K^{3/2} * exp (-Omega (deg_{1/3}(f)^2/K)) for all values of K up to n/64 simultaneously. Previous secret sharing schemes required that K be determined in advance, and only worked for f=AND. Our analysis draws another new connection between approximate degree and concentration phenomena. As a corollary of this result, we show that for any d <= n/64, any degree d polynomial approximating a symmetric function f to error 1/3 must have coefficients of l_1-norm at least K^{-3/2} * exp ({Omega (deg_{1/3}(f)^2/d)}). We also show this bound is essentially tight for any d > deg_{1/3}(f). These upper and lower bounds were also previously only known in the case f=AND. 

Abstract Cyanobacteria are important photoautotrophs in extreme environments such as the McMurdo Dry Valleys, Antarctica. Terrestrial Antarctic cyanobacteria experience constant darkness during the winter and constant light during the summer which influences the ability of these organisms to fix carbon over the course of an annual cycle. Here, we present a unique approach combining community structure, genomic and photophysiological analyses to understand adaptation to Antarctic light regimes in the cyanobacteriumLeptolyngbyasp. BC1307. We show thatLeptolyngbyasp. BC1307 belongs to a clade of cyanobacteria that inhabits near‐surface environments in the McMurdo Dry Valleys. Genomic analyses reveal that, unlike close relatives,Leptolyngbyasp. BC1307 lacks the genes necessary for production of the pigment phycoerythrin and is incapable of complimentary chromatic acclimation, while containing several genes responsible for known photoprotective pigments. Photophysiology experiments confirmedLeptolyngbyasp. BC1307 to be tolerant of short‐term exposure to high levels of photosynthetically active radiation, while sustained exposure reduced its capacity for photoprotection. As such,Leptolyngbyasp. BC1307 likely exploits low‐light microenvironments within cyanobacterial mats in the McMurdo Dry Valleys.